#pragma once

template<typename T>
class MinHeap
{
public:
	MinHeap(int cap)
	{
		data = new T[cap + 1];
		count = 0;
	}
	MinHeap(T d[], int n)
	{
		data = new T[n + 1];
		count = n;
		for (int i = 0; i < n; ++i)
		{
			data[i] = d[i];
		}

		for (int i = count / 2; i >= 1; --i)
		{
			_ShiftDown(i);
		}
	}

	~MinHeap()
	{
		delete[] data;
	}

	bool IsEmpty()
	{
		return count == 0;
	}

	int Size()
	{
		return count;
	}

	void Push(T t)
	{
		data[count + 1] = t;
		count++;
		_ShiftUp(count);
	}

	T Pop()
	{
		assert(!IsEmpty());
		
		T t = data[1];
		data[1] = data[count];
		count--;
		_ShiftDown(1);

		return t;
	}

private:
	void _ShiftUp(int k)
	{
		while (k > 1 && data[k/2] > data[k])
		{
			swap(data[k / 2], data[k]);
			k /= 2;
		}
	}

	void _ShiftDown(int k)
	{
		while (2 * k <= count)
		{
			int j = 2 * k;
			if (j + 1 <= count && data[j+1] < data[j])
			{
				j += 1;
			}
			if (data[k] <= data[j])
			{
				break;
			}
			swap(data[k], data[j]);
			k = j;
		}
	}

private:
	T* data;
	int count;
};

template<typename T>
class HeapSort
{
public:
	void Sort(T data[], int n)
	{
		MinHeap<T> heap(n);

		for (int i = 0; i < n; ++i)
		{
			heap.Push(data[i]);
		}

		for (int i = 0; i < n; ++i)
		{
			data[i] = heap.Pop();
		}
	}
};

template<typename T>
class HeapifySort
{
public:
	void Sort(T data[], int n)
	{
		MinHeap<T> heap(data, n);

		for (int i = 0; i < n; ++i)
		{
			data[i] = heap.Pop();
		}
	}
};
